1. Field of the Invention
The present invention relates to a managing mechanism for a packet forwarding method and a packet forwarding device, and more particularly, to a packet output management mechanism that reduces memory space.
2. Description of the Related Art
As is well known in the field of Ethernet networks, a switch for instance, is used for packet forwarding such that multiple network locations are connected together. The switch can assign dedicated bandwidth to individual ports and establish large and long working networks.
Ethernet packets can be classified into three types, namely the unicast, the multi-cast and the broadcast packets. On the basis of a memory-sharing mechanism (i.e., memory is shared by all output ports of a switch), a switch that receives a packet must determine in advance the destination output port through which the packet should be output, and then store relevant information of the packet into the output queue of the output port such that the output port can output the packets according to information stored.
The processing mechanisms of multi-cast and broadcast packets can be further classified into the following three processing categories.
The first processing mechanism copies the data of the packet into all the destination ports instead of copying the pointer of the packet only. This processing mechanism requires significant memory space and wastes bandwidth in the packet buffer.
The second processing mechanism creates a dedicated multi-cast packet queue such that all information related to the multi-cast packet can be stored into the queue. However, this may cause out-of-order hazards. For example, storage in the multi-cast and unicast queues may not reflect their respective priorities.
The third processing mechanism copies pointers of the multi-cast packets to every output queue. This mechanism is widely used in most of the switches and the detailed operations of the mechanism will be illustrated as follows.
Please refer to FIG. 1. FIG. 1 is a block diagram of a conventional switch 100. As shown in FIG. 1, each of the output ports 0 through 7 of the switch 100 has a corresponding output queue.
When the switch 100 receives a new packet, the switch 100 temporarily stores the packet into a packet buffer 110. In this case, we assume that the packet is stored in a block (e.g., the address of the block is #6 as shown in FIG. 1) of the packet buffer 110, and the packet needs to be outputted through output port 2. Next, the switch 100 determines that the packet needs to be outputted through output port 2 according to a certain look-up table (not shown). Next, the switch 100 reads pointer #6 that corresponds to the packet from a buffer queue 120 and stores the pointer #6 into the output queue of the output port 2.
In this way, when the output port 2 outputs a packet, the output port 2 outputs the packet in the output queue under First-In-First-Out (FIFO) rules. In the example shown in FIG. 1, the output port 2 outputs the packets corresponding to pointers #7, #2 and #6 sequentially.
The above-mentioned mechanism is straight forward and can be easily implemented, however, at the expense of several disadvantages. For example, if a multi-cast packet has to be stored into N output queues, the pointer of the multi-cast packet is copied N times before being stored into the output queues of the output ports which the multi-cast packet is to be outputted through. Therefore, the output queue of each output port must have sufficient storage space for storing the pointers of all the packets which the packet buffer may store. For example, in a most extreme case, all of the packets may be outputted through a same specific output port, so the output queue of the same specific output port must have sufficient storage space to store the pointers of all of the packets.
Assuming that the switch 100 comprises 8 output ports and the embedded packet buffer 110 is able to store 1024 packets, i.e. a 10-bit address is required to specify all the packets, the output queues of all the output ports in the switch 100 will have to occupy 10 bits*1024*8=10 Kbytes of storage space. In the case of multiple priorities (e.g. 8 different priorities), the output queues take up 10 Kbytes*8=80 Kbytes of storage space. Therefore, a massive amount of storage memory is required for the above-mentioned solutions.